/**
* @Arquivo: pl.c
* 
*	Geração e Solução do problema de coloração usando a formulção de representantes 
*
* @author: Marcio Costa Santos
* @data: 20/05/2010
*
*/

#include"pl.h"
#include<stdio.h>

double weigths[MAX_VALUE][MAX_VALUE];/*o vetor de pesos*/
int status;/*o status do problema*/
extern int n;/*o numero de vertices*/
extern int m;/*o numero de arestas*/
extern long va[];/*a ordem dos verties*/
extern FILE* out;/*o arquivo de saida*/

long edgeVar[MAX_VALUE][MAX_VALUE];/*correspondencia verticeXvertice -> aresta*/
long vertexVar[MAX_VALUE*MAX_VALUE+MAX_VALUE][2];/* correspondencia aresta -> vertexXvertex*/
long var = 0;/*numero de variaveis*/

CPXENVptr env;/*o ambiente do problema*/
CPXLPptr lp;/*o problema*/
double x[MAX_VALUE*MAX_VALUE + MAX_VALUE];/*o vetor de pesos*/
double verif[MAX_VALUE];

char buffer[100];/*string para controle de erro*/

/**
*	Verifica se as rotinas do Cplex contem algum erro pelo valor retorndo
*/
int getErro(char* sucessMsg, char* failMsg){
	if(status == 0){}
	else{
		if ( CPXgeterrorstring (env, status, buffer) != NULL ) {
			printf ("%s \n", buffer);
		}else {
			printf ("CPLEX Error %3d:  codigo de erro desconhecido.\n",status);
		}
		printf ("%s \n", failMsg);
	}
	return status;
}

/** 
	Inicia os vetores usados no programa
*/
int prepareVariables(){
	int i, j;
	long ckeck = 0;
	var = 0;
	for(i = 0; i < n; i++){
		for(j = i + 1; j < n; j++){
			edgeVar[va[i]][va[j]] = -1;
			if(hasEdge(va[i],va[j])){
				edgeVar[va[i]][va[j]] = var;
				vertexVar[var][0] = va[i];
				vertexVar[var][1] = va[j];
				var++;
			}else ckeck++;
		}
		edgeVar[va[i]][va[i]] = var;
		vertexVar[var][0] = vertexVar[var][1] = va[i];
		var++;
	}
	return 0;
}

/**
	Adicona as restrições para cada vértice
*/
int addConstrainsForVertex(long vertex){
	int i, j;
	long constrains = 0;/*numero de restrições*/
	long nonNulosCoef =0;/*numero de coeficientes não nulos*/
    	double values[MAX_VALUE*MAX_VALUE];/*os valores nao nulos*/
	int valuesColumns[MAX_VALUE*MAX_VALUE];/*variavel para montar o problema no CPLEX*/
	int valuesRows[MAX_VALUE];/*variavel para montar o problema no CPLEX*/
	double b[MAX_VALUE];/*o lado direito das restricoes*/
	char sense[MAX_VALUE];/*o sinal da desigualdade*/
    if(values == NULL || valuesColumns == NULL || valuesRows == NULL || b == NULL || sense == NULL) return 1;/* verifica se alguns dos vetores é nulo*/
    for(i = vertex + 1; i < n; i++){
       	if(hasEdge(va[vertex],va[i])){
       		for(j = vertex + 1; j < n; j++){
       	   		if((i!=j)&&(!hasEdge(va[i], va[j]))&&(hasEdge(va[vertex], va[j]))){
       	   			if(i < j){
						/*x(v,v) - x(v,w) - x(v,u) >= 0*/
				    	valuesRows[constrains] = nonNulosCoef;
						constrains++;
						values[nonNulosCoef] = 1.0;
						valuesColumns[nonNulosCoef] = edgeVar[va[vertex]][va[vertex]];
						values[nonNulosCoef+1] = -1.0;
						valuesColumns[nonNulosCoef+1] = edgeVar[va[vertex]][va[i]];
						values[nonNulosCoef+2] = -1.0;
						valuesColumns[nonNulosCoef+2] = edgeVar[va[vertex]][va[j]];
						nonNulosCoef += 3;
					 }
          		}
       		}
			valuesRows[constrains] = nonNulosCoef;
			constrains++;
			values[nonNulosCoef] = 1.0;
			valuesColumns[nonNulosCoef] = edgeVar[va[vertex]][va[vertex]];
			values[nonNulosCoef+1] = -1.0;
		  	valuesColumns[nonNulosCoef+1] = edgeVar[va[vertex]][va[i]];
		    	nonNulosCoef += 2;
            	}
    	}
    	valuesRows[constrains] = nonNulosCoef;
    	for(i = 0; i< constrains; i++){
        	b[i] = 0.0;
        	sense[i] = 'G';
    	}
    	status = CPXaddrows(env, lp, 0, constrains, nonNulosCoef, b, sense, valuesRows, valuesColumns, values, NULL, NULL);
       	return getErro("Restriçoes adicionadas com sucesso","Problemas ao adicionar restrições");
}

/**
*	Insire as restrições de representação para cada vértice
*/
int addRepresentantConstrain(long vertex){
	int i;
    long nonNulosCoef = 0;
	double values[MAX_VALUE];/*os valores nao nulos*/
	int valuesColumns[MAX_VALUE];/*variavel para montar o problema no CPLEX*/
	int valuesRows[2];/*variavel para montar o problema no CPLEX*/
	double b[2];/*o lado direito das restricoes*/
	char sense[2];/*o sinal da desigualdade*/
    if(values == NULL || valuesColumns == NULL || valuesRows == NULL || b == NULL || sense == NULL) return 1;/*verifica se algum dos vetores é nulo*/
    valuesRows[0] = 0;
    values[nonNulosCoef] = 1.0;
    valuesColumns[nonNulosCoef] = edgeVar[va[vertex]][va[vertex]];
    nonNulosCoef++;
    for(i = 0; i< vertex; i++){
    	if(hasEdge(va[i], va[vertex])){
       		values[nonNulosCoef] = 1.0;
      		valuesColumns[nonNulosCoef] = edgeVar[va[i]][va[vertex]];
       		nonNulosCoef++;
    	}
    }
    valuesRows[1] = nonNulosCoef;
    for(i = 0; i< 2; i++){
     	b[i] = 1.0;
     	sense[i] = 'E';
    }
    status = CPXaddrows(env, lp, 0, 1, nonNulosCoef, b, sense, valuesRows, valuesColumns, values, NULL, NULL);
	CPXwriteprob (env, lp, "myprob.lp", NULL);
    return getErro("Restriçoes adicionadas com sucesso","Problemas ao adicionar restrições");
}

/**
* Constroi o problema de programação linear
*/
int makePL(long vertex, long edge){
	int i;
	env = CPXopenCPLEX(&status);/*Inicia o ambiente*/
	if(getErro("ILOG/CPLEX iniciado com sucesso","Problemas para abrir o ILOG/CPLEX")==0){
		lp = CPXcreateprob(env, &status,"Formulacao de Representantes");
        	if(getErro("Problema criado com sucesso", "Problemas para criar o problema")==0){
			if(prepareVariables() != 0)return 1;
			double obj[MAX_VALUE + MAX_VALUE*MAX_VALUE];/*a funcao objetivo*/
			double lb[MAX_VALUE + MAX_VALUE*MAX_VALUE];/*o limite inferior das variaveis*/
			double ub[MAX_VALUE + MAX_VALUE*MAX_VALUE];/*o limite superior das variaveis*/
			char type[MAX_VALUE + MAX_VALUE*MAX_VALUE];/*o tipo das variaveis*/
			if(obj == NULL || lb == NULL || ub == NULL || type == NULL) return 1;
			for(i = 0; i < var-1; i++){
				obj[i] = 0.0;
				lb[i] = 0.0;
				ub[i] = 1.0;
				type[i] = 'B';
			}
			for(i = 0; i < n; i++){
				obj[edgeVar[va[i]][va[i]]] = 1.0;
			}
			status = CPXnewcols (env, lp, var, obj, lb, ub, type, NULL);
			if(getErro("Problema montado com sucesso", "Problemas para montado o problema")==0){
				CPXchgobjsen (env, lp, CPX_MIN);
				for(i = 0; i< n; i++){
					if(addRepresentantConstrain(i)!= 0)return 1;
				}
				for(i = 0; i< n; i++){
					if(addConstrainsForVertex(i)!= 0) return 1;
				}
			}
		}
    	}
    	return 0;
}

/**
*	Adiciona uma função callbaxk para poder recuperar os valores reais
*/
int mycallback (CPXENVptr envRelax, void* cbdata, int wherefrom, void* cbhandle, int* useraction_){		CPXLPptr lpRelax;
	status = CPXgetcallbacknodelp (envRelax, cbdata, wherefrom, &lpRelax);
	status = CPXgetcallbacknodex (envRelax, cbdata,wherefrom, x, 0, var-1);
	getErro("Valores do problema adquiridos com sucesso na callback","Problemas para recupara a solucao do problema na callback");
	return 0;
}

/**
*	Seleciona algumas opções do cplex e resolve o problema
*/
int solvePL(){
	CPXsetintparam(env, CPX_PARAM_MIPCBREDLP, CPX_OFF);
	CPXsetintparam(env, CPX_PARAM_DISJCUTS , 2);
	CPXsetintparam(env, CPX_PARAM_FLOWCOVERS  , 2);
	CPXsetintparam(env, CPX_PARAM_FLOWPATHS  , 2);
	CPXsetintparam(env, CPX_PARAM_FRACCUTS  , 2);
	CPXsetintparam(env, CPX_PARAM_GUBCOVERS  , 2);
	CPXsetintparam(env, CPX_PARAM_IMPLBD   , 2);
	CPXsetintparam(env, CPX_PARAM_MIRCUTS  , 2);
	CPXsetintparam(env, CPX_PARAM_SUBALG , 2);
	CPXsetintparam(env, CPX_PARAM_CLIQUES , 2);
	CPXsetintparam(env, CPX_PARAM_COVERS  , 2);
	CPXsetintparam(env, CPX_PARAM_NODELIM, 0);/*opção para limitar a arvore de branch*/
	CPXwriteprob (env, lp, "myprob.lp", NULL);
	status = CPXsetcutcallbackfunc(env, mycallback, NULL);
    getErro("Função adiconada com sucesso","Problemas para adicionar a função");
    status = CPXmipopt(env,lp);
    return getErro("Resolucao do problema efetuada com sucesso","Problemas para resolver a instancia do problema");
}

/**
*	Recupera os valores das variaveis e libera a memoria usada
*/
int getValues(){
	int valid = 0;
	int i,j;
	double value = 0.0;
	for(i = 0; i< n; i++){
		for(j = 0; j< n; j++){
			weigths[va[i]][va[j]] = 0.0;
			verif[i] = 0.0;
		}
	}
	for(j = 0; j< var ; j++){
		weigths[vertexVar[j][0]][vertexVar[j][1]] = x[j];
	}
	for(j = 0; j< n ; j++){
		value += weigths[va[j]][va[j]];
	}	
	fprintf(out,"\nValor da solução encontrado : %f\n", value);
	CPXfreeprob(env,&lp);
	CPXcloseCPLEX(&env);
	return 0;
}



